package middle;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class DiagonalTraverse {
    /**
     * 模拟。
     * 先找出外层循环，然后找出内层循环，和列指针 行指针的移动规律。
     * 参考 ：https://leetcode-cn.com/problems/diagonal-traverse/solution/by-kashingliu-d-b7d3/
     * */
    class Solution {
        public int[] findDiagonalOrder(int[][] mat) {
            int n = mat.length;
            int m = mat[0].length;
            int i = 0,j = 0;
            List<Integer> res = new ArrayList<>();
            for (int circ = 0; circ < n+m-1; circ++){
                // 如果是偶数 那么就是从下往上 如果是奇数 那么从上往下走
                if(circ % 2 == 0){
                    while(i >= 0 && j < m){
                        res.add(mat[i][j]);
                        i--;
                        j++;
                    }
                    // 行 列指针的移动
                    if(j < m){
                        i++;
                    }else{
                        j--;
                        i += 2;
                    }
                }else{
                    while(i < n && j >= 0){
                        res.add(mat[i][j]);
                        i++;
                        j--;
                    }

                    if(i < n){
                        j++;
                    }else{
                        i--;
                        j += 2;
                    }
                }
            }
            return res.stream().mapToInt(Integer::intValue).toArray();
        }
    }
}
